package com.sali.DP;

/**
 * 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
 * <p>
 * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
 * <p>
 * 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
 * <p>
 * 请计算出粉刷完所有房子最少的花费成本。
 */
public class LeetCode_256 {

    int[][] memo; // 记忆化缓存，存储已计算的dp(level, color)结果

    public int minCost(int[][] costs) {
        int len = costs.length;
        if (len == 0) return 0; // 边界：没有房子，成本为0

        memo = new int[len][3]; // 初始化缓存，大小为[房子数][颜色数]

        // 最后一个房子（level = len-1）可以选择三种颜色，取最小成本
        return Math.min(
                Math.min(dp(costs, len - 1, 0), dp(costs, len - 1, 1)),
                dp(costs, len - 1, 2)
        );
    }

    // 递归函数：计算粉刷到第level个房子、选择color颜色的最小成本
    private int dp(int[][] costs, int level, int color) {
        if (level < 0) return 0; // 边界：没有房子时成本为0

        // 如果缓存中已有结果，直接返回（避免重复计算）
        if (memo[level][color] != 0) {
            return memo[level][color];
        }

        // 计算上一个房子的两种可选颜色（不能与当前颜色相同）
        int prevColor1 = (color + 1) % 3; // 例如color=0 → prevColor1=1
        int prevColor2 = (color + 2) % 3; // 例如color=0 → prevColor2=2

        // 当前房子的成本 = 当前颜色成本 + 上一个房子两种颜色的较小成本
        int currentCost = costs[level][color] + Math.min(
                dp(costs, level - 1, prevColor1),
                dp(costs, level - 1, prevColor2)
        );

        // 缓存结果并返回
        memo[level][color] = currentCost;
        return currentCost;
    }

}
